package com.levi.sort;

/**
 * @author shentong
 * @date 2021/8/30 22:09
 * @Description 选择排序
 * 思想:找到最小的值，然后与第一个元素进行交换值
 * 1.需要遍历arr.length轮
 * 2.第一轮需要遍历arr.length - 1,之后第一个元素已经确定，就无需判断，就假定第二个元素是最小值，所以每一轮的遍历次数都 -1
 */
public class SelectSort {
    public static void main(String[] args) {
//        int[] arr = {5, 2, 9, 4, 3, 10, 56, 12};
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 800000);
        }
        long begin = System.currentTimeMillis();
        selectSort(arr);
        long end = System.currentTimeMillis();
        long res = end - begin;
        System.out.printf("选择排序80000个数据消耗时间是%d毫秒\n",res);//3173毫秒

//        print(arr);
    }

    /**
     * 选择排序
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int minIndex = i;//假定第一值是最小值
            for (int j = i+1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {//如果后面的值比假定的最小值小，就重置最小值
                    minIndex = j;
                }
            }
            //一轮循环之后，最小值的索引已经确定了，就和第一个元素交换值
            if (minIndex != i) {
                swap(arr,i,minIndex);
            }
        }
    }

    /**
     * 交换数组中两个下标的值
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * 打印数组
     * @param arr
     */
    public static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
}
